package org.bbelovic.devel.algorithms.recursive;

import java.util.ArrayList;
import java.util.List;

public class App 
{
    public static void main( String[] args )
    {
        String input = "abc";
//        String result = getRemainindString(input, 1);
//        System.out.println(result);
        
        perm1("", input);
//        System.out.println(perms);
    }
    
    
    private static String getRemainindString(String input, int pos) {
        if (pos == 0) {
            return input.substring(1);
        } else {
            String pre = input.substring(0, pos);
            String post = input.substring(pos+1);
            return new String(pre + post);
        }
    }
    
    private static List<String> permutation(String prefix, String input) {
        List<String> col = new ArrayList<String>();
        int length = input.length();
        for (int i = 0; i < length; i++) {
            char act = input.charAt(i);
            String rem = getRemainindString(input, i);
            if (rem.length() == 1) {
                col.add(prefix + rem + act);
            } else {
                List<String> l = permutation(String.valueOf(act), rem);
                col.addAll(l);
            }
        }
        return col;
    }
    
    public  static void perm1(String s) { perm1("", s); }
    private static void perm1(String prefix, String s) {
        int N = s.length();
        if (N == 0) System.out.println(prefix);
        else {
            for (int i = 0; i < N; i++)
               perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
        }

    }
}
